#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

/* Exit gracefully */
void leave(void) {
    fprintf(stderr, "Could not allocate memory\n");
    exit(EXIT_FAILURE);
}

/*
 * We represent an edge as a 3-tuple of integers (u, v, w),
 * where u and v are the vertices connected to by the edge,
 * and w is the weight of the edge.
 */
struct edge {
    int u, v, w;
};

/* We compare two edges by their weight */
int edge_comp(const void *a, const void *b) {
    return ((struct edge *) a)->w - ((struct edge *) b)->w;
}

/* The Union Find Disjoint Set data structure */
struct ufds {
    int *rank, *parent, *size;
    int num_sets;
};

/* Generate a reference to a union find disjoint set with a certain number of elements */
struct ufds *ufds_init(int size) {
    struct ufds *ret = malloc(sizeof(struct ufds));
    if (!ret) {
        leave();
    }
    ret->rank = malloc(sizeof(int) * size);
    if (!ret->rank) {
        free(ret);
        leave();
    }
    ret->parent = malloc(sizeof(int) * size);
    if (!ret->parent) {
        free(ret->rank);
        free(ret);
        leave();
    }
    ret->size = malloc(sizeof(int) * size);
    if (!ret->size) {
        free(ret->parent);
        free(ret->rank);
        free(ret);
        leave();
    }
    ret->num_sets = size;
    for (int i = 0; i < size; i++) {
        ret->parent[i] = i;
    }
    return ret;
}

/* Determine the representative item of a vertex within a union find */
int find_set(int i, struct ufds *uf) {
    if (uf->parent[i] != i) {
        /* Path compression gives us ammortized constant time */
        return uf->parent[i] = find_set(uf->parent[i], uf);
    }
    return i;
}

/* Determine whether two items are within the same set */
int in_same_set(int i, int j, struct ufds *uf) {
    return find_set(i, uf) == find_set(j, uf);
}

/* Bring two sets within the union find together under the same representative item */
int union_set(int i, int j, struct ufds *uf) {
    if (!in_same_set(i, j, uf)) {
        int ri = find_set(i, uf), rj = find_set(j, uf);
        if (uf->rank[ri] < uf->rank[rj]) {
            uf->parent[ri] = rj;
            uf->size[rj]++;
        } else {
            uf->parent[rj] = ri; 
            if (uf->rank[ri] == uf->rank[rj]) {
                uf->rank[rj]++;
                uf->size[rj]++;
            }
        }
        uf->num_sets--;
    }
}

/* Free all allocations within a union find */
void ufds_destroy(struct ufds *uf) {
    free(uf->size);
    free(uf->parent);
    free(uf->rank);
    free(uf);
}

/* An implementatin of kruskal's algorithm - get the cost of an MST represented by an edge list */
int kruskals(int edges, struct edge *elist) {
   struct ufds *uf = ufds_init(edges);
   int cost = 0;
   qsort(elist, edges, sizeof(struct edge), edge_comp);
   for (int i = 0; i < edges; i++) {
       struct edge *e = &elist[i];
       if (!in_same_set(e->u, e->v, uf)) {
            cost += e->w;
            union_set(e->u, e->v, uf);
       }
       if (uf->num_sets == 1) {
           ufds_destroy(uf);
           return cost;
       }
   }
   ufds_destroy(uf);
   return cost;
}

/* Test case 1 */
int test1(void) {
    struct edge elist[] = {{0, 3, 427}, {0, 4, 668}, {0, 5, 495}, {0, 6, 377}, {0, 7, 678}, {0, 9, 177}, {0, 12, 870}, {0, 14, 869}, {0, 15, 624}, {0, 16, 300}, {0, 17, 609}, {0, 18, 131}, {0, 20, 251}, {0, 24, 856}, {0, 25, 221}, {0, 26, 514}, {0, 28, 591}, {0, 29, 762}, {0, 30, 182}, {0, 31, 56}, {0, 33, 884}, {0, 34, 412}, {0, 35, 273}, {0, 36, 636}, {0, 39, 774}, {1, 2, 262}, {1, 5, 508}, {1, 6, 472}, {1, 7, 799}, {1, 9, 956}, {1, 10, 578}, {1, 11, 363}, {1, 12, 940}, {1, 13, 143}, {1, 15, 162}, {1, 16, 122}, {1, 17, 910}, {1, 19, 729}, {1, 20, 802}, {1, 21, 941}, {1, 22, 922}, {1, 23, 573}, {1, 24, 531}, {1, 25, 539}, {1, 26, 667}, {1, 27, 607}, {1, 29, 920}, {1, 32, 315}, {1, 33, 649}, {1, 34, 937}, {1, 36, 185}, {1, 37, 102}, {1, 38, 636}, {1, 39, 289}, {2, 4, 926}, {2, 6, 958}, {2, 7, 158}, {2, 8, 647}, {2, 9, 47}, {2, 10, 621}, {2, 11, 264}, {2, 12, 81}, {2, 14, 402}, {2, 15, 813}, {2, 16, 649}, {2, 17, 386}, {2, 18, 252}, {2, 19, 391}, {2, 20, 264}, {2, 21, 637}, {2, 22, 349}, {2, 26, 108}, {2, 28, 727}, {2, 29, 225}, {2, 30, 578}, {2, 31, 699}, {2, 33, 898}, {2, 34, 294}, {2, 36, 575}, {2, 37, 168}, {2, 38, 432}, {2, 39, 833}, {3, 4, 366}, {3, 7, 635}, {3, 9, 32}, {3, 10, 962}, {3, 11, 468}, {3, 12, 893}, {3, 13, 854}, {3, 14, 718}, {3, 15, 427}, {3, 16, 448}, {3, 17, 916}, {3, 18, 258}, {3, 20, 760}, {3, 21, 909}, {3, 22, 529}, {3, 23, 311}, {3, 24, 404}, {3, 27, 588}, {3, 28, 680}, {3, 29, 875}, {3, 31, 615}, {3, 33, 409}, {3, 34, 758}, {3, 35, 221}, {3, 38, 76}, {3, 39, 257}, {4, 7, 250}, {4, 8, 268}, {4, 10, 503}, {4, 11, 944}, {4, 13, 677}, {4, 15, 727}, {4, 16, 793}, {4, 17, 457}, {4, 18, 981}, {4, 19, 191}, {4, 23, 351}, {4, 24, 969}, {4, 25, 925}, {4, 26, 987}, {4, 27, 328}, {4, 28, 282}, {4, 29, 589}, {4, 31, 873}, {4, 32, 477}, {4, 35, 19}, {4, 36, 450}, {5, 7, 765}, {5, 8, 711}, {5, 9, 819}, {5, 10, 305}, {5, 11, 302}, {5, 12, 926}, {5, 15, 582}, {5, 17, 861}, {5, 19, 683}, {5, 20, 293}, {5, 23, 66}, {5, 25, 27}, {5, 28, 290}, {5, 30, 786}, {5, 32, 554}, {5, 33, 817}, {5, 34, 33}, {5, 36, 54}, {5, 37, 506}, {5, 38, 386}, {5, 39, 381}, {6, 9, 120}, {6, 10, 42}, {6, 12, 134}, {6, 13, 219}, {6, 14, 457}, {6, 15, 639}, {6, 16, 538}, {6, 17, 374}, {6, 21, 966}, {6, 27, 449}, {6, 28, 120}, {6, 29, 797}, {6, 30, 358}, {6, 31, 232}, {6, 32, 550}, {6, 34, 305}, {6, 35, 997}, {6, 36, 662}, {6, 37, 744}, {6, 38, 686}, {6, 39, 239}, {7, 9, 35}, {7, 11, 106}, {7, 12, 385}, {7, 13, 652}, {7, 14, 160}, {7, 16, 890}, {7, 17, 812}, {7, 18, 605}, {7, 19, 953}, {7, 23, 79}, {7, 25, 712}, {7, 26, 613}, {7, 27, 312}, {7, 28, 452}, {7, 30, 978}, {7, 31, 900}, {7, 33, 901}, {7, 36, 225}, {7, 37, 533}, {7, 38, 770}, {7, 39, 722}, {8, 9, 283}, {8, 11, 172}, {8, 13, 663}, {8, 14, 236}, {8, 15, 36}, {8, 16, 403}, {8, 17, 286}, {8, 18, 986}, {8, 21, 810}, {8, 22, 761}, {8, 23, 574}, {8, 24, 53}, {8, 25, 793}, {8, 28, 777}, {8, 29, 330}, {8, 30, 936}, {8, 31, 883}, {8, 32, 286}, {8, 34, 174}, {8, 38, 828}, {8, 39, 711}, {9, 10, 50}, {9, 12, 565}, {9, 13, 36}, {9, 14, 767}, {9, 15, 684}, {9, 16, 344}, {9, 17, 489}, {9, 18, 565}, {9, 21, 103}, {9, 22, 810}, {9, 23, 463}, {9, 24, 733}, {9, 25, 665}, {9, 26, 494}, {9, 27, 644}, {9, 28, 863}, {9, 29, 25}, {9, 30, 385}, {9, 32, 342}, {9, 33, 470}, {9, 37, 730}, {9, 38, 582}, {9, 39, 468}, {10, 11, 155}, {10, 12, 519}, {10, 15, 256}, {10, 16, 990}, {10, 17, 801}, {10, 18, 154}, {10, 19, 53}, {10, 20, 474}, {10, 21, 650}, {10, 22, 402}, {10, 26, 966}, {10, 29, 406}, {10, 30, 989}, {10, 31, 772}, {10, 32, 932}, {10, 33, 7}, {10, 35, 823}, {10, 36, 391}, {10, 39, 933}, {11, 14, 380}, {11, 15, 438}, {11, 17, 41}, {11, 18, 266}, {11, 21, 104}, {11, 22, 867}, {11, 23, 609}, {11, 25, 270}, {11, 26, 861}, {11, 29, 165}, {11, 31, 675}, {11, 32, 250}, {11, 33, 686}, {11, 34, 995}, {11, 35, 366}, {11, 36, 191}, {11, 38, 433}, {12, 13, 313}, {12, 14, 851}, {12, 18, 248}, {12, 19, 220}, {12, 21, 826}, {12, 22, 359}, {12, 23, 829}, {12, 25, 234}, {12, 26, 198}, {12, 27, 145}, {12, 28, 409}, {12, 29, 68}, {12, 30, 359}, {12, 32, 814}, {12, 33, 218}, {12, 34, 186}, {12, 37, 929}, {12, 38, 203}, {13, 14, 132}, {13, 16, 433}, {13, 17, 598}, {13, 20, 168}, {13, 21, 870}, {13, 25, 128}, {13, 26, 437}, {13, 28, 383}, {13, 29, 364}, {13, 30, 966}, {13, 31, 227}, {13, 34, 807}, {13, 35, 993}, {13, 38, 526}, {13, 39, 17}, {14, 16, 596}, {14, 17, 903}, {14, 18, 613}, {14, 19, 730}, {14, 21, 261}, {14, 23, 142}, {14, 24, 379}, {14, 25, 885}, {14, 26, 89}, {14, 28, 848}, {14, 29, 258}, {14, 30, 112}, {14, 32, 900}, {14, 35, 818}, {14, 36, 639}, {14, 37, 268}, {14, 38, 600}, {15, 16, 539}, {15, 17, 379}, {15, 18, 664}, {15, 19, 561}, {15, 20, 542}, {15, 22, 999}, {15, 23, 585}, {15, 26, 321}, {15, 27, 398}, {15, 30, 950}, {15, 31, 68}, {15, 32, 193}, {15, 34, 697}, {15, 36, 390}, {15, 37, 588}, {15, 38, 848}, {16, 18, 73}, {16, 20, 318}, {16, 23, 500}, {16, 25, 968}, {16, 27, 291}, {16, 30, 765}, {16, 31, 196}, {16, 32, 504}, {16, 33, 757}, {16, 35, 542}, {16, 37, 395}, {16, 38, 227}, {16, 39, 148}, {17, 19, 946}, {17, 20, 136}, {17, 21, 399}, {17, 23, 941}, {17, 24, 707}, {17, 25, 156}, {17, 26, 757}, {17, 27, 258}, {17, 28, 251}, {17, 30, 807}, {17, 34, 461}, {17, 35, 501}, {17, 38, 616}, {18, 19, 686}, {18, 22, 575}, {18, 23, 627}, {18, 24, 817}, {18, 25, 282}, {18, 27, 698}, {18, 28, 398}, {18, 29, 222}, {18, 31, 649}, {18, 37, 654}, {19, 21, 389}, {19, 22, 729}, {19, 23, 553}, {19, 24, 304}, {19, 25, 703}, {19, 26, 455}, {19, 27, 857}, {19, 28, 260}, {19, 30, 991}, {19, 31, 182}, {19, 32, 351}, {19, 33, 477}, {19, 34, 867}, {19, 37, 889}, {19, 38, 217}, {19, 39, 853}, {20, 22, 392}, {20, 26, 267}, {20, 27, 407}, {20, 28, 27}, {20, 29, 651}, {20, 30, 80}, {20, 31, 927}, {20, 33, 974}, {20, 34, 977}, {20, 37, 457}, {20, 38, 117}, {21, 23, 202}, {21, 28, 867}, {21, 29, 140}, {21, 30, 403}, {21, 31, 962}, {21, 32, 785}, {21, 34, 511}, {21, 36, 1}, {21, 38, 707}, {22, 23, 388}, {22, 24, 939}, {22, 26, 959}, {22, 28, 83}, {22, 29, 463}, {22, 30, 361}, {22, 33, 512}, {22, 34, 931}, {22, 36, 224}, {22, 37, 690}, {22, 38, 369}, {23, 24, 164}, {23, 25, 829}, {23, 27, 620}, {23, 28, 523}, {23, 29, 639}, {23, 30, 936}, {23, 33, 490}, {23, 35, 695}, {23, 37, 505}, {23, 38, 109}, {24, 26, 616}, {24, 27, 716}, {24, 28, 728}, {24, 30, 889}, {24, 31, 349}, {24, 33, 963}, {24, 34, 150}, {24, 35, 447}, {24, 37, 292}, {24, 38, 586}, {24, 39, 264}, {25, 27, 822}, {25, 31, 736}, {25, 32, 576}, {25, 34, 697}, {25, 35, 946}, {25, 36, 443}, {25, 38, 205}, {25, 39, 194}, {26, 28, 349}, {26, 29, 156}, {26, 30, 339}, {26, 32, 102}, {26, 33, 790}, {26, 34, 359}, {26, 36, 439}, {26, 37, 938}, {26, 38, 809}, {26, 39, 260}, {27, 28, 293}, {27, 29, 486}, {27, 30, 943}, {27, 32, 779}, {27, 34, 6}, {27, 35, 880}, {27, 36, 116}, {27, 37, 775}, {27, 39, 947}, {28, 29, 212}, {28, 30, 684}, {28, 31, 505}, {28, 32, 341}, {28, 33, 384}, {28, 34, 9}, {28, 35, 992}, {28, 36, 507}, {28, 37, 48}, {29, 31, 349}, {29, 32, 723}, {29, 35, 186}, {29, 37, 36}, {29, 38, 240}, {29, 39, 752}, {30, 31, 965}, {30, 32, 302}, {30, 33, 676}, {30, 34, 725}, {30, 36, 327}, {30, 37, 134}, {30, 39, 147}, {31, 32, 474}, {31, 33, 178}, {31, 34, 833}, {31, 37, 555}, {31, 38, 853}, {32, 33, 689}, {32, 37, 451}, {33, 34, 245}, {33, 35, 596}, {33, 36, 445}, {33, 39, 343}, {34, 35, 949}, {34, 37, 270}, {34, 39, 112}, {35, 36, 91}, {35, 38, 768}, {35, 39, 273}, {36, 37, 248}, {36, 39, 344}, {37, 38, 371}, {37, 39, 680}, {38, 39, 540}};
    return kruskals(513, elist);
}

/* Main function */
int main(void) {
    assert(test1() == 2153);
    exit(EXIT_SUCCESS);
}
